#include<stdio.h>
#include <stdlib.h>
typedef struct BiTNode{                //定义结点结构 
	char data;
	struct BiTNode *lchild,*rchild;    //指向左右孩子的指针 
}BiTNode,*BiTree;                    //命名结点类型名，和指向结点的指针类型 

void Release(BiTree &T){            //递归删除该结点及以下结点 
	if(T!=NULL){
        Release(T->lchild);
        Release(T->rchild);
        free(T);
        T=NULL;		//因为free只是告诉系统这块内存我们不用了而不是物（释放了该结点，不在连接到树上） 				//理上面的释放所以我们要手动赋值NULL;  （虽然释放了该结点，但里面还有存放这值，这里置空） 
	}
}

void Delete_X(BiTree &T,char x){    //递归寻找要删除的结点 
	if(T==NULL)                    //1、树为空 
		return;
	
	if(T->data==x){       //2、若T的data为想要删除的元素 则进行删除
		Release(T);   //删除包括根节点
	}
	if(T!=NULL){		 //3、以上情况都不是，递归向左右孩子寻找 
		Delete_X(T->lchild, x);
		Delete_X(T->rchild, x);
	}

}
void CreateBiTree(BiTree &T){  //先序建立二叉树  
	char ch;
	scanf("%c",&ch);          
	if(ch=='#') T=NULL;      //#代表该结点为空 ，也就是父节点没有这个孩子结点 
	else
	{
		T=new BiTNode;
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}
void FirstTraver(BiTree T){  //先序遍历 
	if(T){
		printf("%c",T->data);
		FirstTraver(T->lchild);
		FirstTraver(T->rchild);
	}
} 

int main()
{
	BiTree T; 
	printf("请建立表：\n");
	
	CreateBiTree(T);
	char ch;                
    ch=getchar();        //接收输入数据后回车的影响 
//	BiTree K=T;
	FirstTraver(T);     //先序遍历创建的树 
	printf("\n");
	printf("请输入要删除的节点:\n");
	char del;
	scanf("%c",&del);
	Delete_X(T,del);      //删除该结点及其子树 
	FirstTraver(T);       //先序遍历删除后的结果 
	
}             
